package com.mrzhou.study.struct.linked;

/**
 *  双向链表的实现:
 *  概述: 见 classpath: doc/Java数据结构和算法.pdf  4.4 接节
 */
public class LinkedList<T> {

    private Node<T> header = new Node<>(); // 创建一个带有头结点的双向链表
    private int size; // 双向链表的大小

    public void add(int index, T elem){
        checkPositionIndex(index);
        if(index == size) {
            addLast(elem); return;
        }

        Node<T> current = this.header;
        int i = 0;
        while(current != null && i != index) {
            current = current.next;
            i++;
        }
        Node<T> newNode = new Node<>(elem, current, current.next);
        Node<T> node = current.next; // 获取原来index所在位置的节点
        current.next = newNode;
        node.pre = newNode;
        size++;
    }

    public void addFirst(T elem) {
        if(isEmpty()) {
            this.header.next = new Node<>(elem, this.header, null);
        } else {
            Node<T> newNode = new Node<>(elem, this.header, this.header.next); // 生成新的节点, 新节点的上一节点应是header头, 下一节点为原header头节点的下一节点
            Node<T> node = this.header.next; // 获取原header头节点的下一节点
            this.header.next = newNode; // 获取现在的header头节点的下一节点
            node.pre = newNode;
        }
        size++;
    }

    public void addLast(T elem) {
        Node<T> current = this.header;
        int i = 0;
        while (current.next != null) {
            current = current.next;
            i++;
        }
        current.next = new Node<>(elem, current, null);
        size++;
    }

    public T get(int index) {
        checkElemIndex(index);
        Node<T> current = this.header; // 这里链表的遍历由头节点开始
        int i = 0;
        while (current.next != null && i != index) {
            current = current.next;
            i++;
        }
        return current.next.elem;
    }

    public void remove(int index) {
        checkElemIndex(index);
        Node<T> current = this.header; // 这里链表的遍历由头节点开始
        int i = 0;
        while (current.next != null && i != index) {
            current = current.next;
            i++;
        }
        Node<T> remove = current.next;
        current.next = remove.next;
        if(remove.next != null) {
            remove.next.pre = current;
        }
        remove.next = null;
        remove.pre = null;
        size--;
    }

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(0,2);
        list.add(0,1);
        list.add(1,0);
        list.addFirst(5);
        list.addLast(6);
        System.out.printf("当前链表####\n共有元素: %d个\n元素信息: %s\n", list.size, list);
        System.out.printf("当前链表####\n共有元素: %d个\n逆序输出的元素信息: %s\n", list.size, list.toLastString());
        list.remove(3);
        System.out.printf("当前链表####\n共有元素: %d个\n元素信息: %s\n", list.size, list);
        System.out.printf("当前链表####\n共有元素: %d个\n逆序输出的元素信息: %s\n", list.size, list.toLastString());
    }

    public int size() {
        return this.size;
    }

    /**
     * 判断链表是否为空
     */
    public boolean isEmpty() {
        return this.header.next == null;
    }

    /**
     * 本方法主要是在插入时, 检查index和合法性
     */
    public void  checkPositionIndex(int index) {
        if(!isPositionIndex(index)) {
            throw new ArrayIndexOutOfBoundsException(String.format("超过当前链表的最大长度, 链表最大索引: %d\t入参索引: %d",  size -1 ,  index));
        }
    }

    public void checkElemIndex(int index) {
        if(!isElemIndex(index)) {
            throw new ArrayIndexOutOfBoundsException(String.format("超过当前链表的最大长度, 链表最大索引: %d\t入参索引: %d",  size -1 ,  index));
        }
    }

    /**
     * 检查index的合法性, 正常插入链表时index应该满足大于等于零, 且小于等于size的要求,
     *  注意: 当index == size 的时候, 应该将插入的数据插入到链表的尾部
     */
    private boolean isPositionIndex(int index) {
        return index>= 0 && index <= size;
    }

    /**
     * 判断index的合法性, 正常获取和删除时index不能小于零 同时也不能大于size-1
     */
    private boolean isElemIndex(int index) {
        return index>= 0 && index < size;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("[");
        Node currentNode = this.header.next;
        while(currentNode != null) {
            if(currentNode.next == null) {
                sb.append(currentNode.elem);
            } else {
                sb.append(currentNode.elem).append(", ");
            }
            currentNode = currentNode.next;
        }
        return sb.append("]").toString();
    }

    public String toLastString() {
        StringBuffer sb = new StringBuffer("[");
        Node currentNode = this.header;
        while(currentNode.next!= null) {
            currentNode = currentNode.next;
        }
        while(currentNode.pre != null) {
            if(currentNode.pre.pre == null) {
                sb.append(currentNode.elem);
                break;
            } else {
                sb.append(currentNode.elem).append(", ");
            }
            currentNode = currentNode.pre;
        }
        return sb.append("]").toString();
    }

    private class Node<T> {
        Node() { }
        Node(T elem, Node<T> pre, Node<T> next) {
            this.elem = elem;
            this.pre = pre;
            this.next = next;
        }

        T elem; // 链表节点保存的元素
        Node<T> pre; // 当前节点的上一个节点的指针
        Node<T> next; // 当前节点的下一个节点的指针

        public String toString() {
            if(elem == null) {
                return "";
            }
            return elem.toString();
        }

    }

}
